package com.zhouyong.leetcode.有效的括号20;

import java.util.LinkedList;

/**
 * @author Y5696
 * @date 2023/2/6 10:32
 */

public class Test {
    public static void main(String[] args) {
        // 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
        //
        //有效字符串需满足：
        //
        //左括号必须用相同类型的右括号闭合。
        //左括号必须以正确的顺序闭合。
        //每个右括号都有一个对应的相同类型的左括号。
        System.out.println(isValid("}("));
    }

    public static boolean isValid(String s) {
        // () {} [] ({{}}) (){{{}}} ...
        // 通过栈的方式
        LinkedList<Character> list = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
                list.push(s.charAt(i));
            }
            if ((s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']')) {
                if (list.isEmpty()) {
                    return false;
                }
                Character pop = list.pop();
                switch (pop) {
                    case '(':
                        if (s.charAt(i) != ')') {
                            return false;
                        }
                        break;
                    case '{':
                        if (s.charAt(i) != '}') {
                            return false;
                        }
                        break;
                    case '[':
                        if (s.charAt(i) != ']') {
                            return false;
                        }
                        break;
                    default:
                }
            }
        }
        if (list.isEmpty()) {
            return true;
        }
        return false;
    }
}
